/**
 * //你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 * //
 * // 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表
 * //示如果要学习课程 ai 则 必须 先学习课程 bi 。
 * //
 * //
 * // 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * //
 * //
 * // 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：numCourses = 2, prerequisites = [[1,0]]
 * //输出：true
 * //解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
 * //
 * // 示例 2：
 * //
 * //
 * //输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
 * //输出：false
 * //解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= numCourses <= 10⁵
 * // 0 <= prerequisites.length <= 5000
 * // prerequisites[i].length == 2
 * // 0 <= ai, bi < numCourses
 * // prerequisites[i] 中的所有课程对 互不相同
 * //
 * // Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 👍 1331 👎 0
 */

package com.xixi.basicAlgroithms.BreadthWidthFirstSearch;

import java.util.ArrayList;
import java.util.List;

public class ID00207CourseSchedule {
    public static void main(String[] args) {
        Solution solution = new ID00207CourseSchedule().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        List<List<Integer>> preCoursesList = new ArrayList<>();
        boolean ableFinished = true;
        /*
         * @Desc:
         * 1: 表示被当前启动的节点访问问过
         * 0: 未被访问过；
         * -1: 被其他节点访问过，路径没问题,返回true，不用再继续
         */
        int[] flag = null;


        public boolean canFinish(int numCourses, int[][] prerequisites) {

            //所有课程都没有前置条件，可以学完
            if (prerequisites.length == 0) return true;
            //找出每个课程得前置课程,初始化flag[]
            for (int i = 0; i < numCourses; i++) {
                preCoursesList.add(new ArrayList<>());
            }
            flag = new int[numCourses];
            for (int[] pCourses : prerequisites) {
                preCoursesList.get(pCourses[0]).add(pCourses[1]);
            }

            //每个课程为起点遍历
            for (int i = 0; i < numCourses; i++) {

                if (!dfs(numCourses, prerequisites, i)) return false;

            }


            return ableFinished;

        }

        //环检测
        public boolean dfs(int numCourses, int[][] prerequisites, int nowCourseNo) {
            if (flag[nowCourseNo] == -1) return true; //被其他节点探测过，剪枝，不用再继续了
            if (flag[nowCourseNo] == 1) return false; //被当前节点探测过，成环，返回false;

            flag[nowCourseNo] = 1;
            //剩下是等于0的情况
            List<Integer> preCourses = preCoursesList.get(nowCourseNo);

            for (int i = 0; i < preCourses.size(); i++) {
                int nextCourse = preCourses.get(i);
                //如果检测出环，就不用再继续了，直接return
                if (!dfs(numCourses, prerequisites, nextCourse)) return false;
            }
            flag[nowCourseNo] = -1;
            return true;

        }


    }
//leetcode submit region end(Prohibit modification and deletion)


}